abstract class QuantileSketch
{
    abstract public void insert(double d);
    abstract public double getQuantile(double quant);

    // performs a search to find the largest index that has value less than or equal to r (plus one, to avoid a return of -1)
    public int reverseQuantile(double r, int n)
    {   
        int lo = 0, hi = n - 1;
        while (lo < hi)
	{   
	    int mid = (lo + hi)/2;
	    double v = getQuantile(((double)mid)/n);
	    if (v <= r)
		lo = mid + 1;
	    else if (v > r)
		hi = mid;
	}
	
	return lo;
    }

    // Tests the above function
    public int reverseQuantileTest(double r, int n)
    {
	int lo = 0, hi = n - 1;         
	while (lo < hi)         
	{             
	    int mid = (lo + hi)/2;             
	    double v = getQuantile(((double)mid)/n);  
	    System.out.println(lo + " " + hi + " " + mid + " " + r + " " + v);
	    if (v <= r)
		lo = mid + 1;  
	    else if (v > r)    
		hi = mid;
	}         
	System.out.println("bin search:" + lo);

	for (int i = 0; i < n; i++)             
	    if (getQuantile(((double)i)/n) > r)
	    {
		System.out.println("lin search:" + i);
		if (i != lo)
		{
		    System.out.println("Error!!!");
		    System.exit(0);
		}
		break;
	    }
        return lo; 
    }
}